%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require An undirected or directed graph $G = (V, E)$ that is weighted
  and has no self-loops. Negative edge weights are allowed. The order
  of $G$ is $n > 0$. A vertex $s \in V$ from which to start the
  search. Vertices are numbered from 1 to $n$,
  i.e.~$V = \{1, 2, \dots, n\}$.
\Ensure A list $D$ of distances such that $D[v]$ is the distance of a
  shortest path from $s$ to $v$. A list $P$ of vertex parents such
  that $P[v]$ is the parent of $v$, i.e.~$v$ is adjacent from
  $P[v]$. If $G$ has negative-weight cycles, then return
  \MyFalse. Otherwise, return $D$ and $P$.
%%
%% algorithm body
\State $D \gets [\infty, \infty, \dots, \infty]$\Comment{$n$ copies of $\infty$}
\State $D[s] \gets 0$
\State $P \gets [\,]$
\For{$i \gets 1, 2, \dots, n-1$}
  \State $\MyUpdated \gets \MyFalse$
  \For{\rm each edge $uv \in E$}
    \If{$D[v] > D[u] + w(uv)$}
      \State $D[v] \gets D[u] + w(uv)$
      \State $P[v] \gets u$
      \State $\MyUpdated \gets \MyTrue$
    \EndIf
  \EndFor
  \If{$\MyUpdated = \MyFalse$}
    \State exit the loop
  \EndIf
\EndFor
\For{\rm each edge $uv \in E$}
  \If{$D[v] > D[u] + w(uv)$}
    \State \Return \MyFalse
  \EndIf
\EndFor
\State \Return $(D, P)$
\end{algorithmic}
